1954D - Colored Balls - CodeForces Solution

from math import ceil
MOD = 998244353
N = 5000

n = int(input())
a = [int(x) for x in input().split()]

a.sort()


dp = [0] * (N + 1)

ans = 0
dp[0] = 1
for i in range(n):
    for j in range(N - a[i], - 1, -1):
        dp[j + a[i]] += dp[j]
        dp[j + a[i]] %= MOD


for i in range(N + 1):
    ans += ceil(i / 2) * dp[i]

for i in range(n):
    for j in range(a[i]):
        ans += dp[j] * (a[i] - ceil((j + a[i]) / 2))
        ans %= MOD

print(ans)